Introduction
Minimizing energy
consumption is an important challenge in mobile networking. Significant progress has been made in low-power
hardware design for mobile devices. The wireless network interface is often a
device’s single largest consumer of power. Since the network interface may
often be idle, turning the radio off when not in use could save this power. In practice, however, this approach is not
straightforward. A node must arrange to turn its radio on not just to receive
packets addressed to it, but also to participate in any higher-level routing
and control protocols. The requirement
of cooperation between power saving and routing protocols is particularly acute
in the case of multi-hop ad hoc wireless networks, wherein nodes must forward
packets to each other. Coordination of
power saving with routing in ad hoc wireless networks is the subject of this
paper.
A good power-saving coordination technique for wireless ad-hoc networks ought to have the following characteristics. It should allow as many nodes as possible to turn their radio receivers off most of the time, since even an idle receive circuit can consume almost as much energy as an active transmitter. On the other hand, it should forward packets from any source to any destination with minimally more delay than if all nodes were awake. This implies that enough nodes must stay awake to form a connected backbone. Furthermore, the backbone formed by the awake nodes should provide about as much total capacity as the original network, since otherwise congestion may occur or increase. This means that paths that could operate without interference in the original network should be represented in the backbone.
A good coordination
technique should also not make many assumptions about the link layer’s
facilities for sleeping; it should work with any link-layer that provides for
sleeping and periodic polling. The power saving should inter-operate correctly
with whatever routing system the ad-hoc network uses.
Each node in the network
makes periodic, local decisions on whether to sleep or stay awake as a coordinator
and participate in the forwarding backbone topology. To preserve capacity, a node decides to
volunteer to be a coordinator if it discovers that two of its neighbors cannot
communicate with each other directly or through an existing coordinator. To keep the number of redundant coordinators
low and rotate this role amongst all nodes, each node delays announcing its
willingness with a random delay that takes two factors into account: the amount of remaining battery energy and
the number of pairs of neighbors it can connect together. This combination ensures, with high
probability, a capacity-preserving connected backbone at any point of time. The
nodes are assumed to consume energy at about the same rate. The power saving technique does all this
using only local information, consequently scaling well with the number of
nodes.
Related
Work
The geography informed
energy conservation method [9] uses the node’s geographic location to divide
the world into fixed square grids. The information of each grid stays constant,
regardless of node density. Nodes within grid switch between sleeping and
listening, with the guarantee that one node in each grid must stay in the
listening mode. However, the technique used in this paper will broadcast
messages to discover and direct changes in the network topology using Voronoi diagram. The nodes can be in the random locations.
Also, non-coordinator nodes are ready to receive the packets when operating in
power saving mode.
Design
The network adaptively
elects “Coordinators” from all nodes and the coordinators stay awake
continuously and perform multi-hop packet routing within the ad hoc network,
while other nodes remain in power-saving mode and periodically check if they
should wake up and become a coordinator.
This can be achieved in
the four ways:
- The network ensures that enough
coordinators are elected so that every node is in radio range of at least
one coordinator.
- The network rotates the coordinators in
order to ensure that all nodes share the task of providing global connectivity
roughly equally.
- The network attempts to minimize the
number of nodes elected as coordinators, thereby increasing network
lifetime, but without suffering a significant loss of capacity or an
increase in latency.
- Finally, the network elects coordinators
using only local information in decentralized manner. Each node only
consults state stored in local routing tables during the election process.
In the network, each node
periodically broadcasts HELLO messages that contain the node’s status (i.e.
whether or not the node is a coordinator), its current coordinators and its
current neighbors. These HELLO messages,
and consequently the states maintained are similar to those of proactive ad hoc
routing protocols (e.g., geographic routing [4] or DSDV [6]). Each node maintains only a small amount of
additional state-its coordinators and coordinators of neighbors-in addition to
a list of neighbors normally found in the routing table.
A node switches state
from time to time between being a coordinator and being a non-coordinator. A node includes its current state in its
HELLO messages. The following sections
describe how a node decides that it should announce that it is a coordinator
and how it decides that it should withdraw from being a coordinator.
Coordinator
Announcement
Periodically, a
non-coordinator node determines if it should become a coordinator or not. The following coordinator eligibility rule in
power saving method ensures that the entire network is covered with enough coordinators:
Coordinator eligibility
rule: If two
neighbors of a non-coordinator node cannot reach each other either directly or
via one or two coordinators, the node should become a coordinator.
While this election
algorithm does not yield the minimum number of coordinators required to merely
maintain connectedness, it forms a network that roughly contains a coordinator
in every populated radio range in the entire network topology. Since packets will be routed through coordinators,
this topology ought to yield good capacity.
Announcement contention
occurs where multiple nodes discover the lack of a coordinator at the same time
and all decide to become a coordinator.
We resolve contention by delaying coordinator announcements with a randomized
back-off delay. Each node chooses a
delay value and delays the HELLO message that announces the node’s volunteering
as a coordinator for that amount of time.
If at the end of the delay, the node has not received any HELLO message
from other potential coordinators, it sends the HELLO message. Otherwise, it reevaluates its eligibility
based on any HELLO messages received and makes its announcement if and only if
the eligibility rule still holds.
Coordinator
Withdrawal
Each coordinator
periodically checks if it should withdraw as a coordinator. A node should
withdraw if every pair of its neighbors can reach each other directly or via
some other coordinators. However, in order to also ensure fairness, after a
node has been a coordinator for some period of time, it withdraws if every pair
neighbor nodes can reach each other via some other neighbor, even if those
neighbors are not currently coordinators. This rule gives other neighbors a
chance to become coordinators.
To prevent temporary loss
of connectivity between a coordinator’s withdrawal message and the announcement
from a new coordinator, a node continues to serve as a coordinator for a short
period of time even after announcing its withdrawal. This ‘grace period’ allows
the routing protocol to continue to use the old coordinator until a new
coordinator is elected.
Coordinator
Election
The coordinator election algorithm uses two
criteria for electing coordinators.
- The
source and destination nodes of each flow need to constantly send and
receive packets; they do not operate in power saving mode. Thus, they
automatically become coordinators.
- The
routing algorithm can readily detect that a coordinator has left the
region through MAC layer failure. The election algorithm may not react
fast enough to elect new coordinator. In the worst case, nodes must wait
until the old coordinator information has expired before a new coordinator
can be elected. Even if the
coordinator does not exist, a non-coordinator node announces itself as a
coordinator, if it has received a large number of packets to route in the
recent past. If this coordinator turns out to be redundant, the
coordinator withdrawal algorithm will force the node to withdraw itself as
a coordinator soon after.
Power
saving mode
The power saving protocol
determines when to turn a node’s radio on or off. It depends on the low level
MAC layer to support power saving functions, such as buffering packets for
sleeping nodes. We have implemented the
algorithm on top of the MAC and physical layers with ad hoc power saving
support [1]. The power-saving mode uses periodic beacons to synchronize
nodes in the network. Beacon packets
contain timestamps that synchronize nodes` clocks. A beacon period starts with an Ad hoc Traffic
Indication Message Window (ATIM window), during which all nodes are
listening and pending traffic transmissions are advertised. A node that receives and acknowledges an
advertisement for unicast or broadcast traffic
directed to it must stay on for the rest of the beacon period. Otherwise, it can turn itself off at the end
of the ATIM window, until the beginning of the next beacon period. After the ATIM window, advertised traffic is
transmitted. Since traffic cannot be
transmitted during the ATIM window, the available channel capacity is reduced.
Performance Evaluation
To
measure the effectiveness of the power saving method, we simulate on various
static and mobile topologies on their energy consumption, network lifetime,
etc.
The
power saving method chooses the number of coordinators that would be required
to form a hexagonal grid layout shown in Figure 1. The hexagonal grid layout of
nodes produces a connected backbone in every direction with very few
coordinators.
Figure 1: A layout of coordinators
The
hexagonal grid layout of coordinators places a coordinator at each vertex of a
hexagon. Every coordinator can communicate with other three coordinators that
it is connected to through an edge of a hexagon with equal distance. Each hexagon has six coordinators, but each
coordinator is shared by three hexagons. Therefore, each hexagon is only
responsible for two coordinators. Each hexagon has an area of ‘N’ m2. Suppose the simulated area is d2 meters, then the number of coordinators (Cideal) expected in that area is
Cideal = 2 x (d2/N)
Using
NS-2 simulator [10], we simulate various node densities with different
fractions of energy remaining in different nodes.
Figure 2: Ideal and actual coordinator density as a
function of node density.
Figure
2 shows coordinator density as a function of node density. Coordinator density
is computed from the average number of coordinators elected by the simulated
five mobile stations over 300 seconds. The nodes becomes coordinators not only
because they are sources or destinations, they reside at the left and right
edges of simulation area. The numbers in the figure are only slightly less than
the number of coordinators had there been no sources or sinks. Points on the
“ideal” curve in Figure 4 are computed using the ideal number of coordinators
with equal area distance.
The
power saving method elects more coordinators than are needed. There are two
reasons for this. First, non-uniform density often causes more nodes to become
coordinators. Second, to rotate coordinators among all nodes, the optimal set
of coordinators may not always be selected.
We
have taken the nodes which occupies in the equal distance. In practice, the
nodes are not in equal positions. This increases the number of coordinators.
Using the Voronoi diagram method, we can resolve this
consideration to some extent.
Suppose
the given nodes scattered in an area of ‘N’m2. Let us find out
the coordinators for Figure 3 and Figure4.
Figure3: Scattered nodes and the coordinators
Using
the Voronoi diagram algorithm,
Input: The number of nodes n > 3 of
area and the list of sides S = (s1, s2, . . . , sn) of the area are in the
increasing order with respect to x-coordinates.
Output: Voronoi diagram V or (S) is constructed.
Step 1: Let t be the integral part of n/2 and S is split
into
SL = (s1
, s2 , . . . , st)
and SR = (st+1 , st+2
, . . . , sn).
Step 2: The Voronoi diagram Vor(SL) of SL is constructed recursively.
Step 3: The Voronoi diagram Vor(SR) of SR is
constructed recursively.
Step 4: Vor(SL)
and Vor(SR) are merged into
the Voronoi diagram of Vor(S)
i.e., Vor(S) = Vor(SL) U Vor(SR)
by algorithm MERGE_VORONOI.
Step 5: We return to Vor(S).
Figure 4: Constructed Voronoi
diagram of various nodes and coordinators
Coordinator
density is computed from the average number of coordinators elected by the
simulated six mobile stations over 360 seconds using constructed Voronoi diagram given by Figure 5.
Figure5: Ideal and actual coordinator density as a
function of node density using Voronoi algorithm.
The
non-uniform density often causes more nodes to become coordinators. The
increase is reduced to some extent compared to ordinary power saving method.
Conclusion
This
paper presents a distributed coordination technique for multi-hop ad hoc
networks that reduces energy consumption without significantly diminishing the
capacity or connectivity of the network. In ad hoc network, coordinator is
elected from all nodes and it rotates amongst them in time. The coordinator may
stay awake and perform multi-hop packet routing within the ad hoc network,
while other nodes remain in power-saving mode and periodically check if they
should awaken and become a coordinator.
Each
node uses a random back off to decide whether to become a coordinator. This
delay is a function of the number of other nodes in the neighborhood that can
be bridged using this node and the amount of energy it has remains the
same. The implementation of the power
saving technique periodically wakes up the nodes and makes them to listen the
advertisements and this will increase the cost. This warrants investigation
into a more robust and efficient power saving technique in MAC layer that
minimizes the amount of time each node spends in power saving mode.
References
1.
Benjie Chen, Hari Balakrishnan, Kyle Jamieson and Robert Morries,
Span: An energy-efficient coordination
algorithm for topology maintenance in wireless networks, Technical
report, Massachusetts Institute of Technology, www.lcs.mit.edu, 1999.
2.
Finn, G.G., Routing and Addressing Problems in Large Metropolitan-scale Inter
networks, ISI, March 1987, pp87-180.
3. Shepard, Channel
Access Scheme for Large Dense Packet Radio Networks. Proceeding of the
ACM SIGCOMM, August 1996, pp 219-230.
4. Pamas, S. and Raghavendra Singh,
C., Power Aware Multi-Access Protocol
with signaling for Ad Hoc Networks, ACM Computer Communication Review,
July 1998, pp5-26.
5. Perkins, C., Highly
Dynamic Destination-Sequenced Distance Vector Routing (DSDV) for Mobile
Computers, Proceeding of the ACM SIGCOMM, Vol.24, 1994, London, U.K., pp234-244.
6. Meng, T.H. and Rodoplu, V., Minimum
Energy
7. Ramanathan, R. and Rosales-Hain, R., Tel
8. Estrin, D., Heidemann,
J and Xu, Y., Rom, Geography-informed Energy
conservation for Ad hoc routing. Proceedings of the Seventh Annual ACM/IEEE
International Conference on Mobile Computing and Networking (Mobicom), July 2001,
9. ns :Notes and Documents. www.isi.edu/vint/nsnam/
10. CMU Monarch Extensions to ns. www.monarch.cs.cmu.edu/
11. F.P. Preparata, M.I. Shamos, Computational Geometry, Springer-Verlag, 1985.
12. J.R. Sack, J. Urrutia , Handbook of Computational Geometry, Elsevier Science B.V, 2000.
13. T. Ohya, M. Iri, K. Murota, Improvement of the incremental method for the Voronoi diagram with computational comparison of various algorithms. Journal of Operational Research Society, 1984, pp 306-336.
14. K. Sugihara, M.Iri, Construction of the Voronoi diagram for one million sites in single-precision arithmetic. Proceedings of IEEE, 1992, pp1471-1484.
Technical College - Bourgas,
All rights reserved, © March, 2000